﻿

namespace Common.Algorithm.Core;

 

public class OcTreeNode<T>
{
    public Guid guid { get; set; } = Guid.NewGuid();

    public Cube envelop { get; set; }

    /// <summary>
    /// 当前层数
    /// </summary>
    public int curDepth { get; set; }

    /// <summary>
    /// 最大层数
    /// </summary>
    public static int maxDepth { get; set; } = 12;

    /// <summary>
    /// 获得T的外包
    /// </summary>
    public static Func<T, Cube> getBBoxFunc { get; set; }
    /// <summary>
    /// 当前节点的内容物
    /// </summary>
    public List<T> items { get; set; } = new List<T>();

    //public QuadTreeNode<T> parent { get; set; }
    /// <summary>
    /// 子节点
    /// </summary>
    public OcTreeNode<T>[]? childs { get; set; }

    /// <summary>
    /// 节点内物体最大数量
    /// </summary>
    public int capacity { get; set; } = 4;

    /// <summary>
    /// build
    /// </summary>
    /// <param name="_envelop"></param>
    /// <param name="_curDepth"></param> 
    public OcTreeNode(Cube _envelop, int _curDepth/*, int _maxDepth*/)
    {
        this.envelop = _envelop;
        this.curDepth = _curDepth;
        //maxDepth = _maxDepth;
        childs = null;
        //Items = new List<QuadtreeItem>();//先给个空集合，实例化时还确定不了区域内的对象有哪些
        //Children = null;//用于判断是否有子节点  
    }

    #region 增

    public void Insert(T item)
    {
        var rect = getBBoxFunc(item);
        bool isIntersected = this.envelop.IsIntersect(rect);//两个矩形是否相交
        bool isMaxDepth = curDepth >= maxDepth;//达到最大节点层
        bool isFull = this.items.Count() >= capacity;//满员需要分割为下一层

        //不相交 直接返回
        if (!isIntersected) return;
        //相交  达到最大层    添加到当前 返回
        if (isMaxDepth) { this.items.Add(item); return; }
        //未满 且 无子节点  添加到当前 返回
        if (!isFull && childs == null) { this.items.Add(item); return; }

        //满员 且 无子节点 则创建子节点
        if (isFull && childs == null)
        {
            curDepth = curDepth + 1;
            childs = this.envelop.SplitCube()
                .Select(r => new OcTreeNode<T>(r, curDepth))
                .ToArray();
        }
        //继续
        {
            //如果有子节点就插入到子节点即可
            //当前层的所有物体计入子节点继续划分 
            items.Add(item);
            var tmpItems = items.Select(t => t).ToList();
            items.Clear();//清空当前子节点
            foreach (var child in childs)
            {
                foreach (var tmpItem in tmpItems)
                {
                    var tmpRect = getBBoxFunc(tmpItem);
                    //物体框在四分边界处 item就直接保持在当前
                    bool isOnEdge = this.childs.Where(c => c.envelop.IsIntersect(tmpRect)).Count() > 1;
                    if (isOnEdge) { this.items.Add(tmpItem); continue; }

                    //继续递归
                    child.Insert(tmpItem);
                }
            }
        }
    }

    #endregion

    #region  删

    /// <summary>
    /// 删除某一物体
    /// </summary>
    /// <param name="item"></param>
    public void Remove(T item)
    {
        bool hasItem = this.items.Contains(item);
        if (hasItem)
        {
            items.Remove(item); return;
        }
        else
        {
            if (childs == null) return;
            foreach (var child in childs)
            {
                child.Remove(item);
            }
            //当节点下所有子节点都没有物体时 消除子节点分支
            if (childs.All(c => c.items.Count == 0)) { childs = null; }
        }
    }

    #endregion

    #region 查询 query

    /// <summary>
    /// 查询某一物体所在节点
    /// </summary>
    /// <param name="item"></param>
    /// <returns></returns>
    public OcTreeNode<T> QueryNodeBy(T item)
    {
        OcTreeNode<T> node = this;
        bool hasItem = items.Contains(item);
        if (hasItem) { return this; }
        else
        {
            foreach (var child in childs)
            {
                node = child.QueryNodeBy(item);
            }
            return node;
        }
    }

    /// <summary>
    /// 查询某物体同节点内的物体  包括传入的物体
    /// </summary>
    /// <param name="item"></param>
    /// <returns></returns>
    public List<T> QueryItemsBy(T item)
    {
        var node = QueryNodeBy(item);
        return node.items;
    }

    /// <summary>
    /// 查询所有节点
    /// </summary>
    /// <returns></returns>
    public List<OcTreeNode<T>> GetAllNodes()
    {
        List<OcTreeNode<T>> nodes = new List<OcTreeNode<T>>();
        nodes.Add(this);
        if (childs != null && childs.Count() != 0)
        {
            foreach (var child in childs)
            {
                nodes.AddRange(child.GetAllNodes());
            }
        }
        return nodes;
    }

    #endregion



}